package my;

import java.util.Stack;

/**
 * Recursion Test
 *
 * @author AJun
 * @date 2020/11/15
 */
public class AlgoMain02 {

    public static void main(String[] args) {
        // int n = 3;
        // System.out.println(sum(n));
        // System.out.println(sum2(n));
        // System.out.println(sum3(n));

        int n = 4;
        log(n);
        log1(n);
        log2(n);
    }

    /**
     * 递归实例
     * 空间复杂度: O(n)
     */
    static void log(int n) {
        if (n < 1) return;
        log(n - 1);
        int v = n + 10;
        System.out.println(v);
    }

    /**
     * 递归转非递归，重复利用一个变量来保存每个帧栈的内容
     * 空间复杂度: O(1)
     */
    static void log2(int n) {
        for (int i = 1; i <= n; i++) {
            System.out.println(i + 10);
        }
    }

    /**
     * 递归转非递归，使用一个栈来模拟函数调用栈，保存每次调用的参数或局部变量
     * 空间复杂度: O(n)
     */
    static void log1(int n) {
        Stack<Frame> frames = new Stack<>();
        while (n > 0) {
            frames.push(new Frame(n, n + 10));
            n--;
        }
        while (!frames.isEmpty()) {
            Frame frame = frames.pop();
            System.out.println(frame.v);
        }
    }

    static class Frame {
        int n;
        int v;

        public Frame(int n, int v) {
            this.n = n;
            this.v = v;
        }
    }

    /**
     * 求 1 + 2 + 3 + ... + (n - 1) + n 的值
     */
    static int sum(int n) {
        if (n <= 1) return n;
        return n + sum(n - 1);
    }

    static int sum2(int n) {
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += i;
        }
        return sum;
    }

    static int sum3(int n) {
        if (n <= 1) return n;
        return ((1 + n) * n) >> 1;
    }

}
